A Copositive Approach for Two-Stage Adjustable Robust Optimization with Uncertain Right-Hand Sides

摘要

We study two-stage adjustable robust linear programming in which theright-hand sides are uncertain and belong to a convex, compact uncertainty set.This problem is NP-hard, and the affine policy is a popular, tractableapproximation. We prove that under standard and simple conditions, thetwo-stage problem can be reformulated as a copositive optimization problem,which in turn leads to a class of tractable, semidefinite-based approximationsthat are at least as strong as the affine policy. We investigate severalexamples from the literature demonstrating that our tractable approximationssignificantly improve the affine policy. In particular, our approach solvesexactly in polynomial time a class of instances of increasing size for whichthe affine policy admits an arbitrarily large gap.